Communication networks are generally designed as point-to-point networks to interconnect, upon request, selected pairs of terminals from a large plurality of terminals connected to the network. The simplest network capable of connecting N network inlets to N network outlets is an N.times.N crossbar array of switching elements or crosspoints. Although such an array is non-blocking in that any idle inlet is always connectable to any idle outlet regardless of other array interconnections, the crossbar array is not a practical network in many applications due to the prohibitive cost of the large number of array crosspoints.
One known non-blocking network having significantly fewer crosspoints than a crossbar array is disclosed in an article by C. Clos, "A Study of Non-Blocking Switching Networks," Bell System Technical Journal, March 1953, pages 406-424. The network, referred to as the three-stage Clos network, has N inlets and M outlets and comprises N/n rectangular n.times.r first stage switches, r rectangular N/n.times.M/m second stage switches and M/m rectangular r.times.m third stage switches. There is exactly one link connecting each first stage switch to each second stage switch and one link connecting each second stage switch to each third stage switch. A three-stage Clos network where the number, r, of second stage switches is given by r=n+m-1, is a non-blocking point-to-point network. This is true since a given first stage switch input terminal is always connectable to a given third stage switch output terminal via a second stage switch that is connected to none of the other n-1 input terminals of the given first stage switch and none of the other m-1 output terminals of the given third stage switch. A five-stage Clos network can be constructed by replacing each second stage switch with a three-stage Clos network. More generally, an S+2 stage Clos network can be recursively constructed from an S stage Clos network by replacing each switch in a given stage with a three-stage Clos network. However, Clos networks are difficult to implement in, for example, the photonics domain because the switching elements are typically quite large, and there are different numbers of links between stages, with the number of links increasing geometrically toward the center of the network. Efficient photonic network implementations typically have small, non-complex switching elements, e.g., 2.times.2 nodes, and are relatively space-invariant from stage to stage. The interest in photonic networks is mainly stimulated by their potential to implement massively parallel architectures. This holds especially true for free space systems where three-dimensional space is the communications medium and where imaging setups use bulk optical elements such as lenses, mirrors, and beam splitters to interconnect two-dimensional arrays of optical logic devices.
Another known network architecture is the so-called perfect shuffle. A perfect shuffle network of 2.times.2 nodes is a cost-effective interconnection network, for example, in large-scale parallel and distributed supercomputer systems, because it provides network connectivity from any of N network inlets to any of N network outlets in only log.sub.2 N stages. The inter-stage interconnection pattern assigns links consecutively to nodes in the next stage in a manner analogous to shuffling a deck of playing cards. There are a number of other known networks, such as the banyan and the crossover, which are topologically equivalent to the perfect shuffle although they each have their own specific interconnection pattern. For each of these networks, the number of inter-stage links between any pair of successive stages is equal to N, the number of network inlets. Photonic implementations of such networks using free-space optical interconnects are disclosed in U.S. patent application Ser. No. 296,284 of K. Brenner et al., filed Jan. 11, 1989, "Optical Shuffle Arrangement" and U.S. patent application Ser. No. 219,623 of J. Jahns et al., filed July 15, 1988, "Optical Crossover Network", both applications being assigned to the same assignee as the present invention. Networks of this type are, however, not fault-tolerant and have high blocking. The problem with the topology is that in a network having log.sub.2 N stages, there is only one path from a given network inlet to a given network outlet. Thus, if there is a fault on that path or some part of the path is busy, no communication is possible. An article of G. B. Adams et al., "The Extra Stage Cube: A Fault-Tolerant Interconnection Network for Supersystems", IEEE Transactions on Computers, Vol. C-31, No. 5, May 1982, discloses the addition of an extra stage to the network thus providing one additional path between any inlet and any outlet. Although this makes the network substantially more reliable, it still has an unacceptably high blocking probability. Furthermore, the simple addition of extra stages will never result in a point-to-point, strictly nonblocking network or even one with a blocking probability that is acceptably low in most high-traffic network applications.
In view of the foregoing, a recognized problem in the art is the lack of a low-blocking or non-blocking network that is efficiently implementable in the photonics domain.